More and more programs are utilizing source code constructs that are written in high level, dynamically-typed programming languages that must be compiled or interpreted before many other activities (e.g., layout calculations, rendering) associated with the constructs can be executed. By way of example, ECMAscript-based scripting languages (e.g., JavaScript® or Flash) are frequently used in connection with the content that they host. One of the most ubiquitous dynamically-typed languages is JavaScript which is run by a JavaScript engine that may be realized by a variety of technologies including interpretation-type engines, profile-guided just-in-time (JIT) compilation (e.g., trace based or function based), and traditional-function-based JIT compilation where native code is generated for the entire body of all the functions that get executed. Other dynamically-typed programming languages can be run by similar engines.
In virtual machines for dynamically-typed programming languages (e.g., JavaScript), performance is largely determined by characteristics of the global type state. Global type state can be thought of as a description of all program behavior and invariants across either a single run of a program or multiple runs. In a statically-typed programming language, global type state includes classes, class members, types of members, parameters, and variables, as well as any other type or structural information expressed explicitly or implicitly in the program source code. Programs written in static languages are usually faster to execute than those written in dynamic languages because type information is fully specified in source code at compile-time, and optimized code is generated based on it. Additionally, since type state doesn't change at run-time in statically typed programs, run-time type checks are not necessary. However, programmers sometimes prefer to use dynamically-typed languages rather than statically-typed languages for several reasons, such as increased flexibility and simplicity. One tradeoff to using dynamically-typed languages is that the aspects of the global type state can change, which makes the compilation of optimized code imprecise, and sometimes wasteful.
In order to generate optimized code for a dynamically-typed language, some type information needs to be known, and several ways of determining type state have been implemented. In a dynamically-typed language virtual machine (VM), global type state can be inferred from program behavior with some analysis that can involve estimation and speculation and with the possibility that the data type of certain variables or other properties can change during program execution. Hence, it is possible to generate optimized code at any point during program execution, but that code may be invalidated when global type state changes. Consequently, the VM must detect when the program deviates from the current global type state using run-time type checks. When a type check fails, the VM must update the global type state by taking the union of the old type state and the new change. Any optimized code dependent on the old type state must be invalidated, and execution must be transferred to non-optimized code. This process, known as deoptimization, is costly in terms of time spent and processing resources used to discard optimized code and generate new optimized code. Deoptimization may happen frequently when a program is starting up until it reaches a fairly complete, steady type state.
Existing virtual machines maintain global type state in a format which is specific to a single run or context of a program. When a short program is run repeatedly, deoptimization is particularly frequent and costly because type state is discarded between runs, and the program may not reach a steady state until it is nearly finished. As dynamically-typed programs become more popular, the current methods of type state analysis and deoptimization will require improvement, and will almost certainly be unsatisfactory in the future.